/*
 * =====================================================================================
 *
 *       Filename:  twoArrSumMinusMin.c
 *
 *    Description:  given two array a and b, swap value in a and b, so that the absolute value of sum a minus sum b is min
 *
 *        Version:  1.0
 *        Created:  2012年03月29日 17时37分20秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:  
 *
 * =====================================================================================
 */

#include	"utility.h"

void doSwap(int *a, int *b, int n, int **ab, int *ba)
{
    long sumA = 0, sumB = 0;
    int  *high, *low;
    long sumhigh, sumlow;
    int **table;
    int k;
    for (k = 0; k < n; ++k) {
        sumA += a[k];
        sumB += b[k];
    }

    if (sumA == sumB) 
        return;

    if (sumB < sumA){
        high = a; sumhigh = sumA;
        low = b;  sumlow = sumB;
    } else {
        high = b; sumhigh = sumB;
        low = a; sumlow = sumA;
    }
    
    do {
        int delta = sumhigh - sumlow;
        if (high == a) table = ab;
        else table = ba;
        int i, j;
        for (i = 0; i < n; ++i)
        {
            for (j = 0; j < n; ++j)
            {
                if (table[i][j] > 0 && table[i][j] < delta)
                    break;
            }
            if (j < n)
                break;
        }
        if (i >= n)
            break;
        mySwap(high+i, low+j);
        sumhigh += (low[j] - high[i]);
        sumlow += (high[i] - low[j]);
        if (sumlow == sumhigh)
            break;
        else if (sumlow > sumhigh)
        {
            int *temp = high;
            high = low;
            low = temp;
            mySwap(&sumlow, &sumhigh);
        }
    } while(1);

    return;
}

void test()
{

}
